package main.java;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-10-02 11:11
 */


import java.util.HashSet;

/**
 * 题目：
 * 给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 * 图示两个链表在节点 c1 开始相交：
 */
public class Test37_两个链表的第一个重合点 {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        ListNode ls1 = headA;
        ListNode ls2 = headB;
        HashSet<ListNode> hs = new HashSet<>();
        while (ls1 != null) {
            hs.add(ls1);
            ls1 = ls1.next;
        }

        while (ls2 != null) {
            if (hs.contains(ls2)) {
                return ls2;
            }
            ls2 = ls2.next;
        }

        return null;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }

        return a;
    }

}
